package com.learn._2list;

import com.learn._2list.LinkedList;

public class PolynomialCalculator {



    private static class Polynomial<T> extends LinkedList<T> {



    }


    private static class PolynomialItem{
        double c; //系数
        int e;//指数


        public static PolynomialItem create(double c, int e){
            PolynomialItem newItem = new PolynomialItem();
            newItem.c = c;
            newItem.e = e;
            return newItem;
        }
    }


    public static void main(String[] args) {
        //构造两个多项式
        Polynomial<PolynomialItem> first = new Polynomial();
        first.add(PolynomialItem.create(1,150));
        first.add(PolynomialItem.create(1,2));
        first.add(PolynomialItem.create(1,0));

        Polynomial<PolynomialItem> second = new Polynomial<>();
        second.add(PolynomialItem.create(3,3));
        second.add(PolynomialItem.create(2,2));
        second.add(PolynomialItem.create(1,1));

        //加法
        Polynomial<PolynomialItem> addRes = polyAdd(first,second);


        //输出
        LinkedList.LinkNode<PolynomialItem> head = addRes.getNode(0);
        while(head != null){
            System.out.println("加法系数："+head.value.c+" 指数："+head.value.e);
            head = head.next;
        }


        //乘法
        Polynomial<PolynomialItem> multiRes = polyMulti1(first,second);

        LinkedList.LinkNode<PolynomialItem> headM = multiRes.getNode(0);
        while(headM != null){
            System.out.println("乘法系数："+headM.value.c+" 指数："+headM.value.e);
            headM = headM.next;
        }



        //输出
    }


    private static Polynomial<PolynomialItem> polyMulti1(Polynomial<PolynomialItem> first, Polynomial<PolynomialItem> second) {

        if(first == null || second == null){
            return null;
        }
        //默认两者一定有值
        LinkedList.LinkNode<PolynomialItem> firstTmp = first.getNode(0);
        LinkedList.LinkNode<PolynomialItem> secondTmp = second.getNode(0);


        Polynomial<PolynomialItem> res = new Polynomial<>();

        while(firstTmp != null){

            Polynomial<PolynomialItem> tmp = new Polynomial<>();
            secondTmp = second.getNode(0);
            while(secondTmp != null){
                PolynomialItem newItem = PolynomialItem.create(firstTmp.value.c * secondTmp.value.c,firstTmp.value.e + secondTmp.value.e);
                tmp.add(newItem);
                secondTmp = secondTmp.next;

            }
            res = polyAdd(res,tmp);
            firstTmp = firstTmp.next;
        }

        return res;

    }

    private static Polynomial<PolynomialItem> polyMulti(Polynomial<PolynomialItem> first, Polynomial<PolynomialItem> second) {

        if(first == null || second == null){
            return null;
        }
        //默认两者一定有值
        LinkedList.LinkNode<PolynomialItem> firstTmp = first.getNode(0);
        LinkedList.LinkNode<PolynomialItem> secondTmp = second.getNode(0);


        Polynomial<PolynomialItem> res = new Polynomial<>();
        LinkedList.LinkNode<PolynomialItem> secondRear = secondTmp;
        while(secondRear != null){
            res.add(PolynomialItem.create(firstTmp.value.c * secondRear.value.c,firstTmp.value.e + secondRear.value.e));
            secondRear = secondRear.next;
        }

        firstTmp = firstTmp.next;
        while(firstTmp != null){

            secondRear = secondTmp;
            while(secondRear != null){
                PolynomialItem newItem = PolynomialItem.create(firstTmp.value.c * secondRear.value.c,firstTmp.value.e + secondRear.value.e);
                if(res.size() <= 0){
                    res.add(newItem);
                }else {
                    LinkedList.LinkNode<PolynomialItem> resHead = res.getNode(0);
                    while(resHead != null && resHead.value.e > newItem.e){
                        resHead = resHead.next;
                    }
                    if(resHead == null){
                        //每个都大于新加的
                        res.add(newItem);
                    }else if(resHead.value.e == newItem.e){
                        //相等，合并
                        resHead.value.c = resHead.value.c + newItem.c;
                    }else{
                        //比新加的小，将新加的插入到前面
                        LinkedList.LinkNode node = new LinkedList.LinkNode();
                        node.value = newItem;
                        resHead.pre.next = node;
                        node.pre = resHead.pre;
                        node.next = resHead;
                        resHead.pre = node;
                    }
                    secondRear = secondRear.next;

                }
            }
            firstTmp = firstTmp.next;
        }

        return res;

    }

    private static Polynomial<PolynomialItem> polyAdd(Polynomial<PolynomialItem> first, Polynomial<PolynomialItem> second) {

        if(first.size() == 0){
            return second;
        }else if(second.size() == 0){
            return first;
        }

        LinkedList.LinkNode<PolynomialItem> firstTmp = first.getNode(0);
        LinkedList.LinkNode<PolynomialItem> secondTmp = second.getNode(0);

        Polynomial<PolynomialItem> res = new Polynomial<>();
        while(firstTmp != null || secondTmp != null){
            if(firstTmp == null){
                secondTmp = addToResultAndGoToNext(secondTmp,  res);
            }else if(secondTmp == null){
                firstTmp = addToResultAndGoToNext(firstTmp, res);
            }else{
                int firstE,secondE;
                if( (firstE = firstTmp.value.e) > (secondE = secondTmp.value.e)){
                   firstTmp = addToResultAndGoToNext(firstTmp,res);
                }else if(firstE == secondE){
                    PolynomialItem newItem = PolynomialItem.create(firstTmp.value.c + secondTmp.value.c,firstE);
                    res.add(newItem);
                    firstTmp = firstTmp.next;
                    secondTmp = secondTmp.next;
                }else{
                    secondTmp = addToResultAndGoToNext(secondTmp,res);
                }


            }
        }
        return res;



    }

    private static LinkedList.LinkNode<PolynomialItem> addToResultAndGoToNext(LinkedList.LinkNode<PolynomialItem> secondTmp, Polynomial<PolynomialItem> res) {
        res.add(PolynomialItem.create(secondTmp.value.c, secondTmp.value.e));
        secondTmp = secondTmp.next;
        return secondTmp;
    }
}
